/**
 * 
 */
package uk.ac.manchester.cs.graph.alg;

import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

import uk.ac.manchester.cs.graph.DirectedGraph;
import uk.ac.manchester.cs.graph.Edge;

/**
 * @author Pavel Klinov
 *
 */
public class TransitiveReductionAlgorithm <V,E> {

	private ReductionHandler<V, E> mHandler = null;
	
	public TransitiveReductionAlgorithm() {}
	
	public TransitiveReductionAlgorithm(ReductionHandler<V, E> handler) {
		mHandler = handler;
	}
	
	public void compute(DirectedGraph<V,E> graph, Collection<V> startVertices) {
		Map<V, Set<V>> dcMap = computeDistantChildren(graph, startVertices);

		for (V vertex : dcMap.keySet()) {			
			processVertex(vertex, graph, dcMap);
		}
	}
	
	public void compute(DirectedGraph<V,E> graph) {
		compute(graph, graph.getRoots());
	}
	
	private void processVertex(V vertex, DirectedGraph<V,E> graph, Map<V, Set<V>> dcMap) {
		Set<V> distant = dcMap.get(vertex);
		
		for (V next : graph.getAdjacentVertices(vertex)) {
			
			if (distant.contains(next)) {
				Edge<V,E> edge = graph.findEdge(vertex, next);
				
				if (mHandler != null) {
					mHandler.onEdgeRemove(edge);
				}
				
				graph.removeEdge(edge);
			}
		}
	}
	
	private Map<V, Set<V>> computeDistantChildren(DirectedGraph<V,E> graph, Collection<V> startVertices) {
		Map<V, Set<V>> dcMap = new HashMap<V, Set<V>>();
		
		for (V vertex : startVertices) {			
			computeDistantChildren(vertex, graph, dcMap);
		}
		
		return dcMap;
	}

	private void computeDistantChildren(V vertex, DirectedGraph<V, E> graph, Map<V, Set<V>> dcMap) {
		
		if (dcMap.containsKey(vertex)) return;
		
		if (isBottom(vertex, graph)) {			
			dcMap.put(vertex, new HashSet<V>());
			
		} else {			
			Set<V> distantChildren = new HashSet<V>();
			
			for (V child : graph.getAdjacentVertices(vertex)) computeDistantChildren(child, graph, dcMap);
			
			for (V child : graph.getAdjacentVertices(vertex)) {			
				distantChildren.addAll(dcMap.get(child));
				distantChildren.addAll(graph.getAdjacentVertices(child));
			}
			
			dcMap.put(vertex, distantChildren);
		}
	}

	private boolean isBottom(V vertex, DirectedGraph<V,E> graph) {
		return graph.getAdjacentVertices(vertex).isEmpty();
	}
	
	public interface ReductionHandler<V,E> {
		public void onEdgeRemove(Edge<V,E> edge);
	}
}


